package com.zhang.sort;

/**
 * @author zhang
 * @time 2022/01/11 19:41:10
 */
public class QuickSort {
    public void sort(int[] array) {
        sort(array,0,array.length-1);
    }
    private void sort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        //Partition
        int boundary = partition(array,start, end);
        //Sort left
        sort(array, start, boundary - 1);
        //Sort right
        sort(array,boundary + 1, end);
    }

    private int partition(int[] array,int start, int end) {
        int pivot = array[end];
        int boundary = start -1 ;
        for (int i = start; i <= end; i++) {
            if (array[i] <= pivot) {
                swap(array,i,++boundary);
            }
        }
        //index of pivot
        return boundary;
    }
    public void swap(int[] array, int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}
